#!/usr/bin/python
# -*- coding:UTF-8 -*-
#第七章 决策树建模
# 不同于其他大多数分类器，由决策树产生的模型具有易于解释的特点--贝叶斯分类器中的数字列表会告诉我们每个单词的重要程度
# 但是你必须经过计算才能确知结果到底如何
# 理解神经网络的难度则更大,因为位于两个神经元之间的连接上的权重值本身并没有什么实际意义。而对于决策树，我们只须要通过
# 观察就可以理解其推导的过程，

# 本章的三个例子：1、预测一个网站有多少用户有可能会愿意为了某些高级功能支付费用
#                 2、利用决策树为住房定价
#                 3、Hot or Not网站的“热度”评价

from PIL import Image,ImageDraw

my_data = [['slashdot', 'USA', 'yes', 18, 'None'],
           ['google', 'France', 'yes', 23, 'Premium'],
           ['digg', 'USA', 'yes', 24, 'Basic'],
           ['kiwitobes', 'France', 'yes', 23, 'Basic'],
           ['google', 'UK', 'no', 21, 'Premium'],
           ['(direct)', 'New Zealand', 'no', 12, 'None'],
           ['(direct)', 'UK', 'no', 21, 'Basic'],
           ['google', 'USA', 'no', 24, 'Premium'],
           ['slashdot', 'France', 'yes', 19, 'None'],
           ['digg', 'USA', 'no', 18, 'None'],
           ['google', 'UK', 'no', 18, 'None'],
           ['kiwitobes', 'UK', 'no', 19, 'None'],
           ['digg', 'New Zealand', 'yes', 12, 'Basic'],
           ['google', 'UK', 'yes', 18, 'Basic'],
           ['kiwitobes', 'France', 'yes', 19, 'Basic']]

#构造决策树的函数会返回一个根节点，我们可以沿着它的True分支或False分支一直遍历下去,直到
#到达最终结果为止

# 树上的每一个节点
class decisionnode:
	def __init__(self,col=-1,value=None,results=None,tb=None,fb=None):
		#待检验的判断条件(the criteria to be tested)所对应的列索引值
		self.col = col
		#为了使结果为true,当前列必须匹配的值
		self.value = value
		#保存的是针对于当前分支的结果,它是一个字典.除叶节点外,在其它节点上该值都为None
		self.results = results
		#tb和fb也是decisionnide,它们对应于结果分别为true和false时,树上相对于当前节点的子树上的节点
		self.tb = tb
		self.fb = fb
		
# CART(Classification and Regression Trees 分类回归树）
# 功能：在某一列上对数据集合进行拆分，能够处理数值型数据或名词性数据
#       根据列表中某一栏的数据将列表拆分成两个数据集
#       该函数接受一个列表，一个指示表中列所在位置的数字,和一个用以对列进行拆分的参考值作为
#       参数
# 返回：返回两个列表,一个列表包含指定列中的数据将会与我们先前指定的参考会值相匹配的数据行
#                    另一个列表是不相匹配的
# 流程：上述代码创建了一个名为split_function的函数,该函数根据数据集的类型(是否是数值型),对其
#       进行拆分.（非数值型,判断指定列中数值是否与参考值相等）
def divideset(rows, column, value):
    # 定义一个函数，令其告诉我们数据行属于第一组(返回值为true)还是第二组(返回值为false)
    split_function = None
    if isinstance(value, int) or isinstance(value, float):
        split_function = lambda row: row[column] >= value
    else:
        split_function = lambda row: row[column] == value

    # 将数据集分成两个集合，并返回
    set1 = [row for row in rows if split_function(row)]
    set2 = [row for row in rows if not split_function(row)]
    return (set1, set2)


# 对各种可能的结果进行计数（每一行数据的最后一列记录了这一计数结果）
# 功能：找到所有不同的可能结果,并返回一个字典,其中包含了每一项结果的出现次数
#       其他函数可以利用该函数计算数据集合的混杂程度
def uniquecounts(rows):
    results = {}
    for row in rows:
        # 计数结果在最后一列
        r = row[len(row) - 1]
        if r not in results: results[r] = 0
        results[r] += 1
    return results


#==================选择合适的拆分方案==================================
#熵与基尼不纯度之间的主要区别在于,熵达到峰值的过程要相对慢一些。
#因此,熵对于混乱集合的“判罚”往往要重一些

# 基尼不纯度
# 功能：该函数利用集合中每一项结果出现的次数除以集合的总行数来计算相应的概率,
#       随机放置的数据项出现于错误分类中的概率
def giniimpurity(rows):
    total = len(rows)
    counts = uniquecounts(rows)
    imp = 0
    for k1 in counts:
        p1 = float(counts[k1]) / total
        for k2 in counts:
            if k1 == k2: continue
            p2 = float(counts[k2]) / total
            imp += p1 * p2
    return imp

# 熵代表的是集合的无序程度，
# 熵是遍历所有可能的结果之后所得到的p(x)log(p(x))之和
def entropy(rows):
    from math import log
    log2 = lambda x: log(x) / log(2)
    results = uniquecounts(rows)

    # 此处开始计算熵的值
    ent = 0.0
    for r in results.keys():
        p = float(results[r]) / len(rows)
        ent = ent - p * log2(p)
    return ent

#================构造分类树================================
# 生成树
# 原理：为了弄明白一个属性的好坏程度,我们的算法首先求出整个群组的熵，
#       然后尝试利用每个属性的可能取值对群组进行拆分，并求出新群组的熵。
#				并求出两个新群组的熵。
#	  		（为了确定哪个属性最适合用来拆分，算法会计算相应的信息增益：指当前熵与两个新群组经过加权平均后的熵之间的差值）
#       算法会针对每个属性计算相应的信息增益,然后从中选出信息增益最大的属性）
# 流程：1、首先创建一个根节点
#       2、然后通过评估表中的所有观测变量,从中选出最合适的变量对数据进行拆分
#				3、当拆分某个节点所得的信息增益不大于0的时候,对分支的拆分才会停止
def buildtree(rows, scoref=entropy):
    if len(rows) == 0: return decisionnode()
    current_score = scoref(rows)

    # 定义一些变量以记录最佳拆分条件
    best_gain = 0.0
    best_criteria = None
    best_sets = None

    column_count = len(rows[0]) - 1
    for col in range(0, column_count):
        # 在当前列中生成一个由不同值构成的序列
        column_values = {}
        for row in rows:
            column_values[row[col]] = 1
        # 接下来根据这一列中的每个值，尝试对数据集进行折分
        for value in column_values.keys():
            (set1, set2) = divideset(rows, col, value)

            # 信息增益
            p = float(len(set1)) / len(rows)
            gain = current_score - p * scoref(set1) - (1 - p) * scoref(set2)
            if gain > best_gain and len(set1) > 0 and len(set2) > 0:
                best_gain = gain
                best_criteria = (col, value)
                best_sets = (set1, set2)

        # 创建子分支
    if best_gain > 0:
        trueBranch = buildtree(best_sets[0])
        falseBranch = buildtree(best_sets[1])
        return decisionnode(col=best_criteria[0], value=best_criteria[1],
                            tb=trueBranch, fb=falseBranch)
    else:
        return decisionnode(results=uniquecounts(rows))


# 剪枝
def prune(tree, mingain):
    # 如果分支不是叶节点,则对其进行剪枝操作
    if tree.tb.results == None:
        prune(tree.tb, mingain)
    if tree.fb.results == None:
        prune(tree.fb, mingain)

    # 如果两个子支点都是叶节点,则判断它们是否须要合并
    if tree.tb.results != None and tree.fb.results != None:
        # 构造合并后的数据集
        fb, tb = [], []
        for v, c in tree.tb.results.items():
            tb += [[v]] * c
        for v, c in tree.fb.results.items():
            fb += [[v]] * c

        # 检查熵的减少情况
        delta = entropy(tb + fb) - (entropy(tb) + entropy(fb) / 2)

        if delta < mingain:
            # 合并分支
            tree.tb, tree.fb = None, None
            tree.results = uniquecounts(tb + fb)

#================决策树的显示=====
# 绘制决策树,以纯文本的方式显示树
def printtree(tree, indent=''):
    # 这是一个叶节点吗？
    if tree.results != None:
        print(str(tree.results))
    else:
        # 打印判断条件
        print(str(tree.col) + ':' + str(tree.value) + '? ')

        # 打印分支
        print(indent + 'T->',end='')
        printtree(tree.tb, indent + '  ')
        print(indent + 'F->',end='')
        printtree(tree.fb, indent + '  ')


#====== 图形表示法
# 节点在垂直方向上所需要的空间
def getwidth(tree):
    if tree.tb == None and tree.tb == None: return 1
    return getwidth(tree.tb) + getwidth(tree.fb)

#分支的深度等于其最长子分支的总深度值加1
def getdepth(tree):
    if tree.tb == None and tree.fb == None: return 0
    return max(getdepth(tree.tb), getdepth(tree.fb)) + 1


def drawnode(draw, tree, x, y):
    if tree.results == None:
        # 得到每个分支的宽度
        w1 = getwidth(tree.fb) * 100
        w2 = getwidth(tree.tb) * 100

        # 确定此节点所要占据的总空间
        left = x - (w1 + w2) / 2
        right = x + (w1 + w2) / 2

        # 绘制判断条件字符串
        draw.text((x - 20, y - 10), str(tree.col) + ':' + str(tree.value), (0, 0, 0))

        # 绘制到分支的连线
        draw.line((x, y, left + w1 / 2, y + 100), fill=(255, 0, 0))
        draw.line((x, y, right - w2 / 2, y + 100), fill=(255, 0, 0))

        # 绘制分支的节点
        drawnode(draw, tree.fb, left + w1 / 2, y + 100)
        drawnode(draw, tree.tb, right - w2 / 2, y + 100)
    else:
        txt = ' \n'.join(['%s:%d' % v for v in tree.results.items()])
        draw.text((x - 20, y), txt, (0, 0, 0))

def drawtree(tree, jpeg='tree.jpg'):
    w = getwidth(tree) * 100
    h = getdepth(tree) * 100 + 120

    img = Image.new('RGB', (w, h), (255, 255, 255))
    draw=ImageDraw.Draw(img)

    drawnode(draw,tree,w/2,20)
    img.save(jpeg,'JPEG')




#=========== 对新的观测数据进行分类================
# 功能：接受新的观测数据作为参数,然后根据决策树对其进行分类
# 流程：1、该函数采用与printtree完全相同的方式对树进行遍历
#       2、每次调用之后,函数会根据调用结果来判断是否到达分支的末端，它会对观测数据作出评估
#       3、确认列数据是否与参考值相匹配,如果匹配,则会再次在True分支上调用classify,如果不匹配,则会在False分支上调用classify
def classify(observation, tree):
    if tree.results == None:
        return tree.results
    else:
        v = observation[tree.col]
        branch = None
        if isinstance(v, int) or isinstance(v, float):
            if v >= tree.value:
                branch = tree.tb
            else:
                branch = tree.fb
        else:
            if v == tree.value:
                branch = tree.tb
            else:
                branch = tree.fb
        return classify(observation, branch)


# 带有缺失数据的分类方法
def mdclassify(observation, tree):
    if tree.results != None:
        return tree.results
    else:
        v = observation[tree.col]
        if v == None:
            tr, fr = mdclassify(observation, tree.tb), mdclassify(observation, tree.fb)
            tcount = sum(tr.values())
            fcount = sum(fr.values())
            tw = float(tcount) / (tcount + fcount)
            fw = float(fcount) / (tcount + fcount)
            result = {}
            for k, v in tr.items(): result[k] = v * tw
            for k, v in fr.items():
                if k not in result: result[k] = 0
                result[k] += v * fw
            return result
        else:
            if isinstance(v, int) or isinstance(v, float):
                if v >= tree.value:
                    branch = tree.tb
                else:
                    branch = tree.fb
            else:
                if v == tree.value:
                    branch = tree.tb
                else:
                    branch = tree.fb
            return mdclassify(observation, branch)


# 处理数值型结果
def variance(rows):
    if len(rows) == 0: return 0
    data = [float(row[len(row) - 1]) for row in rows]
    mean = sum(data) / len(data)
    variance = sum([(d - mean) ** 2 for d in data]) / len(data)
    return variance